import collections


class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        n1 = len(nums1)
        n2 = len(nums2)
        k1_max = min(k, n1)
        k1_min = max(k - n2, 0)

        def search(nums, k, n):
            stack = collections.deque()
            for i in range(n):
                while stack and nums[i] > stack[-1] and len(stack) + n - i - 1 >= k:
                    stack.pop()
                if len(stack) < k:
                    stack.append(nums[i])
            return stack

        def combine(s1, s2, k1, k2):
            stack = collections.deque()
            left_index = 0
            right_index = 0
            while left_index < k1 and right_index < k2:
                if s1[left_index] > s2[right_index]:
                    stack.append(s1[left_index])
                    left_index += 1
                else:
                    if s1[left_index] < s2[right_index]:
                        stack.append(s2[right_index])
                        right_index += 1
                    else:
                        t1 = left_index + 1
                        t2 = right_index + 1
                        while t1 < k1 and t2 < k2:
                            if s1[t1] > s2[t2]:
                                stack.append(s1[left_index])
                                left_index += 1
                                break
                            else:
                                if s1[t1] < s2[t2]:
                                    stack.append(s2[right_index])
                                    right_index += 1
                                    break
                                else:
                                    t1 += 1
                                    t2 += 1
                        if t1 <= k1 and t2 == k2:
                            stack.append(s1[left_index])
                            left_index += 1
                        if t1 == k1 and t2 < k2:
                            stack.append(s2[right_index])
                            right_index += 1

            while left_index < k1:
                stack.append(s1[left_index])
                left_index += 1
            while right_index < k2:
                stack.append(s2[right_index])
                right_index += 1
            return tuple(stack)

        max_out = None
        for k1 in range(k1_min, k1_max + 1):
            k2 = k - k1
            s1 = search(nums1, k1, n1)
            s2 = search(nums2, k2, n2)
            out = combine(s1, s2, k1, k2)
            if not max_out:
                max_out = out
            else:
                max_out = max(out, max_out)
        return list(max_out)


data = Solution()
# nums1 = [3, 4, 6, 5]
# nums2 = [9, 1, 2, 5, 8, 3]
# k = 5
# print(data.maxNumber(nums1, nums2, k))
# nums1 = [2, 5, 6, 4, 4, 0]
# nums2 = [7, 3, 8, 0, 6, 5, 7, 6, 2]
# k = 15
# print(data.maxNumber(nums1, nums2, k))
nums1 = [3, 8, 5, 3, 4]
nums2 = [8, 7, 3, 6, 8]
k = 5
print(data.maxNumber(nums1, nums2, k))
